문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 RSA 암호화 (문단 편집) === 암호화 및 해독 === 공개키를 이용해 RSA 방식으로 암호화를 하는 과정은 다음과 같다. > 보내려는 평서문 [math( a )]를 [math( x ≡ a^e\ \pmod N )]으로 암호화한다. (여기서 [math(a < N)]이어야 한다.[* 만약 보내려는 평서문의 길이가 N보다 길면, 모종의 복잡한 변환법을 통해 분할하여 N보다 짧게 만든다. 당연하지만 해당 변환법은 보내는 측과 받는 측 모두 알고 있어야 한다.][* [math( x ≡ a^e\ \pmod N )] 는 [math(x)]와 [math(a^e)]를 각각 [math(N)]으로 나눴을 때 나머지가 같다는 뜻이다. "[math(x)]와 [math(a^e)]는 법[math(N)]에 대하여 [[합동식|합동]]이다" 라고 읽는다.]) 예를 들어 앨리스가 공개키를 만들어 뿌렸고, 밥이 앨리스한테 메세지를 비밀리에 주고 싶다고 하자.[* 대부분의 암호학 문서에서 메세지를 주고 받는 사람의 이름으로 '앨리스'와 '밥'을 쓴다.] 밥은 앨리스의 공개키를 통해 암호화된 내용([math(x)])를 앨리스한테 준다. 그러면 앨리스는 자신이 가지고 있는 개인키를 이용해 원래 평서문을 얻을 수 있다. RSA 방식으로 해독을 하는 과정은 다음과 같다. > 받은 암호문 [math(x)]를 [math(a' ≡ x^d\ \pmod N )]으로 복호화한다. 그러면 [math(a' = a)]가 되어 앨리스는 밥의 메세지를 무사히 받을 수 있게 된다. 프로그래밍을 어느 정도 해 본 사람이라면 [math(a^e\bmod N)]나 [math(x^d \bmod N)] 같은 걸 어떻게 계산하나 싶을 것이다. [math(a^e)] 같은 걸 계산하는 걸 곱셈을 [math(e)] 번 하는 식의 터무니없이 막대한 연산을 수행할 수는 없는 노릇이고 그렇다고 pow 같은 걸 쓰자니 자릿수가 턱없이 모자랄 것이기 때문이다.[* [math(e = 3)] 같은 경우라면 모를까 일반적으로 [math(d)]는 몇 백에 달하는 자릿수를 가진 어마어마한 수일 것이고 [math(x^d)] 같은 걸 정확하게 계산하려면 '''전 세계에 있는 메모리를 다 모아도 부족할 정도로''' 어마어마한 저장 공간이 필요할 것이다.] 이렇게 보면 RSA 방식이 필요로 하는 연산이 불가능해 보이지만 의외로 간단한데다 연산량도 그리 크지가 않아 오히려 매우 실용적이다. 어느 수의 제곱을 구할때 밑의 수를 계속 곱하면 지수가 1씩 증가해서 시간복잡도가 [math(O(n))]이지만, 기존의(우리가 구해놓은) 제곱한 수를 제곱하게 되면 지수가 2배씩 증가해서 시간복잡도가 [math(O(\log n))]이 되기 때문이다. 이 방식을 설명하는 것은 간단한 예를 하나 드는 것이 빠를 것 같다. 예를 들어 [math(x)]의 23제곱을 [math(N)]으로 나눈 나머지를 계산하고 싶다고 하자. 그러면 [math(ab\bmod N = (a\bmod N)(b\bmod N)\bmod N)], [math(a^b\bmod N = (a\bmod N)^b\bmod N)]로부터 다음을 얻는다. [math(x^{23}\bmod N = x^{2^0 + 2^1 + 2^2 + 2^4}\ mod\ N = (x \cdot x^2 \cdot (x^2)^2 \cdot (((x^2)^2)^2)^2)\ mod\ N)] [math(= ((x\ mod\ N) ((x\ mod\ N)^2\ mod\ N) (((x\ mod\ N)^2\ mod\ N)^2\ mod\ N) (((((x\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)\ mod\ N.)] 뭔가 복잡해 보인다. 여기서 [math(x_0 = x\ mod \ N)], [math(x_{i + 1} = x_i^2\ mod\ N)]이라 표기하면 사실 위 식은 이렇게 깔끔하게 정리된다. [math(x^{23}\ mod\ N = (x_0 x_1 x_2 x_4)\ mod\ N.)] 즉 [math(x_i)]들을 계산해 놓고 이들을 활용하면 엄청난 계산량이라든가 저장 공간 같은 것 없이 저렴하게 [math(x^d\ mod\ N)] 등을 계산할 수 있다. 이걸 다음과 같은 알고리즘으로 정리할 수 있다. 1. [math(y ≡ x\ mod\ N)]을 계산한다. 1. [math(m = 1, r = 1)]로 둔다. 1. 만약 [math(d)]의 (2진법에서) [math(m)]번째 자릿수가 1이라면 [math(ry\ mod\ N)]을 계산한 다음 [math(r)]에 저장한다. 1. [math(y)]에 [math(y^2\ mod\ N)]을 저장한다. 1. [math(m)]에 [math(m + 1)]를 저장한다. 1. 만약 [math(m)]가 [math(d)]의 자릿수보다 크지 않으면 3으로 돌아가고 그렇지 않으면 종료한다. 알고리즘이 종료하면 원하는 결과가 [math(r)]에 저장되어 있을 것이다. 이렇게 하면 기껏해야 [math(N)]의 자릿수의 두 배 정도를 저장할 수 있는 공간에 [math(d)]의 자릿수 정도만큼 반복하는 연산 만으로도 [math(x^d\ mod\ N)]를 계산할 수 있다. 다만 [math(N)]의 자릿수의 두 배에 달하는 용량을 가진 두 정수 변수의 곱셈과 나눗셈은 기본적으로 하드웨어에서 지원하지 않는데다 이 사칙연산들마저도 연산량이 장난 아니다. 그래서 이런 알고리즘을 써도 상당한 연산을 요구하며 이 때문에, 후술하겠지만, RSA만으로 모든 암호화를 하진 못 하고 대신 다른 암호화 방식과 연동하여 쓰는 것이 보통이다. 대학에서 이산수학을 수강할시 기말고사로 풀라고 문제가 나오는 경우도 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기